{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Events That Can Be Attended II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多可以参加的会议数目 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>events</code> 数组，其中 <code>events[i] = [startDay<sub>i</sub>, endDay<sub>i</sub>, value<sub>i</sub>]</code> ，表示第 <code>i</code> 个会议在 <code>startDay<sub>i</sub></code><sub> </sub>天开始，第 <code>endDay<sub>i</sub></code> 天结束，如果你参加这个会议，你能得到价值 <code>value<sub>i</sub></code> 。同时给你一个整数 <code>k</code> 表示你能参加的最多会议数目。</p>\n",
    "\n",
    "<p>你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 <strong>完整</strong> 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。</p>\n",
    "\n",
    "<p>请你返回能得到的会议价值 <strong>最大和</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/02/06/screenshot-2021-01-11-at-60048-pm.png\" style=\"width: 400px; height: 103px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>events = [[1,2,4],[3,4,3],[2,3,1]], k = 2\n",
    "<b>输出：</b>7\n",
    "<strong>解释：</strong>选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/02/06/screenshot-2021-01-11-at-60150-pm.png\" style=\"width: 400px; height: 103px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>events = [[1,2,4],[3,4,3],[2,3,10]], k = 2\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>参加会议 2 ，得到价值和为 10 。\n",
    "你没法再参加别的会议了，因为跟会议 2 有重叠。你 <strong>不</strong> 需要参加满 k 个会议。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/02/06/screenshot-2021-01-11-at-60703-pm.png\" style=\"width: 400px; height: 126px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3\n",
    "<b>输出：</b>9\n",
    "<b>解释：</b>尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= k <= events.length</code></li>\n",
    "\t<li><code>1 <= k * events.length <= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 <= startDay<sub>i</sub> <= endDay<sub>i</sub> <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 <= value<sub>i</sub> <= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-events-that-can-be-attended-ii](https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-events-that-can-be-attended-ii](https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,4],[3,4,3],[2,3,1]]\\n2', '[[1,2,4],[3,4,3],[2,3,10]]\\n2', '[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    res = 0\n",
    "    \n",
    "    def maxAncestorDiff(self,root:TreeNode)->int:\n",
    "        if not root: return 0\n",
    "        self.dfs(root,root.val, root.val)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self,root, maxValue, minValue):\n",
    "        maxValue = max(root.val, maxValue)\n",
    "        minValue = min(root.val, minValue)\n",
    "        if root.left is None and root.right is None:\n",
    "            self.res = max(self.res, abs(maxValue - minValue))\n",
    "        if root.left:\n",
    "            self.dfs(root.left,maxValue,minValue)\n",
    "        if root.right:\n",
    "            self.dfs(root.right,maxValue,minValue)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理\n",
    "def getCore(num):\n",
    "    d = 2\n",
    "    res = 1\n",
    "    while d < num:\n",
    "        cnt = 0\n",
    "        while num % d == 0:\n",
    "            num //= d\n",
    "            cnt += 1\n",
    "        if cnt&1:\n",
    "            res *= d\n",
    "        d += 1\n",
    "    # if num > 1:\n",
    "    res *= num\n",
    "    return res\n",
    "\n",
    "maxValue = int(1e4)\n",
    "        \n",
    "# 获取同一组对应的所有下标值\n",
    "group = defaultdict(list)\n",
    "for num in range(1,maxValue+1):    \n",
    "    group[getCore(num)].append(num)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历每个下标分组\n",
    "        for varr in group.values():\n",
    "            # 分组求和\n",
    "            t = 0\n",
    "            for i in varr:\n",
    "                if i > n:\n",
    "                    break\n",
    "                t += nums[i-1]\n",
    "            res = max(res,t)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxValue = int(1e4)\n",
    "        \n",
    "# 获取[1, maxValue]内所有质数\n",
    "tmp = [1] * (maxValue + 1)        \n",
    "prime = []\n",
    "\n",
    "for i in range(2,maxValue + 1):\n",
    "    if tmp[i] == 1:\n",
    "        prime.append(i)\n",
    "\n",
    "    for j in prime:\n",
    "        if j*i > maxValue:\n",
    "            break\n",
    "\n",
    "        tmp[i*j] = 0\n",
    "\n",
    "        if i % j == 0:\n",
    "            break\n",
    "\n",
    "# 根据core分组\n",
    "group = defaultdict(list)\n",
    "# 质因数分解\n",
    "for num in range(1,maxValue+1):    \n",
    "    cur = num\n",
    "    tmp = 1\n",
    "    for p in prime:\n",
    "        cnt = 0\n",
    "        while num % p == 0:\n",
    "            cnt += 1\n",
    "            num //= p\n",
    "        if cnt&1:\n",
    "            tmp *= p\n",
    "        if num < p:\n",
    "            break\n",
    "    \n",
    "    group[tmp].append(cur)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历每个下标分组\n",
    "        for varr in group.values():\n",
    "            # 分组求和\n",
    "            t = 0\n",
    "            for i in varr:\n",
    "                if i > n:\n",
    "                    break\n",
    "                t += nums[i-1]\n",
    "            res = max(res,t)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理\n",
    "def getCore(num):\n",
    "    d = 2\n",
    "    res = 1\n",
    "    while d < num:\n",
    "        cnt = 0\n",
    "        while num % d == 0:\n",
    "            num //= d\n",
    "            cnt += 1\n",
    "        if cnt&1:\n",
    "            res *= d\n",
    "        d += 1\n",
    "    # if num > 1:\n",
    "    res *= num\n",
    "    return res\n",
    "\n",
    "maxValue = int(1e4)\n",
    "        \n",
    "# 获取同一组对应的所有下标值\n",
    "group = defaultdict(list)\n",
    "for num in range(1,maxValue+1):    \n",
    "    group[getCore(num)].append(num)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历每个下标分组\n",
    "        for varr in group.values():\n",
    "            # 分组求和\n",
    "            t = 0\n",
    "            for i in varr:\n",
    "                if i > n:\n",
    "                    break\n",
    "                t += nums[i-1]\n",
    "            res = max(res,t)\n",
    "        \n",
    "        return res# 预处理\n",
    "maxValue = int(1e4)\n",
    "        \n",
    "# 获取[1, maxValue]内所有质数\n",
    "tmp = [1] * (maxValue + 1)        \n",
    "prime = []\n",
    "\n",
    "for i in range(2,maxValue + 1):\n",
    "    if tmp[i] == 1:\n",
    "        prime.append(i)\n",
    "\n",
    "    for j in prime:\n",
    "        if j*i > maxValue:\n",
    "            break\n",
    "\n",
    "        tmp[i*j] = 0\n",
    "\n",
    "        if i % j == 0:\n",
    "            break\n",
    "\n",
    "# 根据core分组\n",
    "group = defaultdict(list)\n",
    "# 质因数分解\n",
    "for num in range(1,maxValue+1):    \n",
    "    cur = num\n",
    "    tmp = 1\n",
    "    for p in prime:\n",
    "        cnt = 0\n",
    "        while num % p == 0:\n",
    "            cnt += 1\n",
    "            num //= p\n",
    "        if cnt&1:\n",
    "            tmp *= p\n",
    "        if num < p:\n",
    "            break\n",
    "    \n",
    "    group[tmp].append(cur)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历每个下标分组\n",
    "        for varr in group.values():\n",
    "            # 分组求和\n",
    "            t = 0\n",
    "            for i in varr:\n",
    "                if i > n:\n",
    "                    break\n",
    "                t += nums[i-1]\n",
    "            res = max(res,t)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class FreqStack:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "        self.value_to_count = {}\n",
    "\n",
    "    def push(self, val: int) -> None:\n",
    "        self.stack.append(val)\n",
    "        self.value_to_count[val] = self.value_to_count.get(val, 0) + 1\n",
    "\n",
    "    def pop(self) -> int:\n",
    "        if not self.stack:\n",
    "            return None\n",
    "        maxValue=max(self.value_to_count.values())\n",
    "        res=-1\n",
    "        for i in range(len(self.stack) - 1, -1, -1):\n",
    "            if self.value_to_count[self.stack[i]]==maxValue:\n",
    "                self.value_to_count[self.stack[i]]-=1\n",
    "                res=self.stack[i]\n",
    "                del self.stack[i]\n",
    "                break\n",
    "        return res\n",
    "\n",
    "\n",
    "# Your FreqStack object will be instantiated and called as such:\n",
    "# obj = FreqStack()\n",
    "# obj.push(val)\n",
    "# param_2 = obj.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class FreqStack:\n",
    "    def __init__(self):\n",
    "        self.value_to_count = {}\n",
    "        self.value_to_pop={}\n",
    "\n",
    "    def push(self, val: int) -> None:\n",
    "        self.value_to_count[val] = self.value_to_count.get(val, 0) + 1\n",
    "        if self.value_to_pop.get(self.value_to_count[val]) is None: \n",
    "            self.value_to_pop[self.value_to_count[val]]=[]\n",
    "        self.value_to_pop[self.value_to_count[val]].append(val)\n",
    "\n",
    "    def pop(self) -> int:\n",
    "        maxValue=max(self.value_to_pop.keys())\n",
    "        res=self.value_to_pop[maxValue].pop()\n",
    "        self.value_to_count[res]-=1\n",
    "        if len(self.value_to_pop[maxValue])==0:\n",
    "            self.value_to_pop.pop(maxValue)\n",
    "        return res\n",
    "\n",
    "\n",
    "# Your FreqStack object will be instantiated and called as such:\n",
    "# obj = FreqStack()\n",
    "# obj.push(val)\n",
    "# param_2 = obj.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class FreqStack:\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "        self.value_to_count = {}\n",
    "        self.value_to_pop={}\n",
    "\n",
    "    def push(self, val: int) -> None:\n",
    "        self.stack.append(val)\n",
    "        self.value_to_count[val] = self.value_to_count.get(val, 0) + 1\n",
    "        if self.value_to_pop.get(self.value_to_count[val]) is None: \n",
    "            self.value_to_pop[self.value_to_count[val]]=[]\n",
    "        self.value_to_pop[self.value_to_count[val]].append(val)\n",
    "\n",
    "    def pop(self) -> int:\n",
    "        if not self.stack:\n",
    "            return None\n",
    "        maxValue=max(self.value_to_pop.keys())\n",
    "        res=self.value_to_pop[maxValue].pop()\n",
    "        self.value_to_count[res]-=1\n",
    "        if len(self.value_to_pop[maxValue])==0:\n",
    "            self.value_to_pop.pop(maxValue)\n",
    "        return res\n",
    "\n",
    "\n",
    "# Your FreqStack object will be instantiated and called as such:\n",
    "# obj = FreqStack()\n",
    "# obj.push(val)\n",
    "# param_2 = obj.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        # dp + 二分查找\n",
    "        n = len(events)\n",
    "        events.sort(key = lambda x:x[0])   # 按照开始时间排序\n",
    "        #print(events)\n",
    "        startTime = [events[i][0] for i in range(n)]\n",
    "        # dp[i] = value,表示参加了会议events[i]之后可以获得的最大会议价值value\n",
    "        dp = [e[2] for e in events]\n",
    "        ans = 0\n",
    "        #print(dp)\n",
    "        for _ in range(k - 1):\n",
    "            for i in range(n - 1,-1,-1):    # 要倒序\n",
    "                e = events[i][1]\n",
    "                nxt = bisect.bisect_right(startTime,e)\n",
    "                for choose in range(n - 1,nxt - 1,-1):  # 要倒序\n",
    "                    dp[choose] = max(dp[choose],dp[i] + events[choose][2])\n",
    "            #print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        wei = [event[1] for event in events]\n",
    "        tou = [event[0] for event in events]\n",
    "        n = len(events)\n",
    "        cont = []\n",
    "        for i in range(n):\n",
    "            cont.append(bisect.bisect_left(wei, tou[i]))\n",
    "        ans = [[0 for _ in range(n+1)] for __ in range(k+1)]\n",
    "        for i in range(1, k+1):\n",
    "            for j in range(1, n+1):\n",
    "                s, e, v = events[j-1]\n",
    "                ans[i][j] = max(ans[i][j-1], v + ans[i-1][cont[j-1]])\n",
    "        return ans[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events=sorted(events)\n",
    "        n=len(events)\n",
    "        @functools.cache\n",
    "        def dp(start,count):\n",
    "            if count==k: return 0\n",
    "            if (temp:=bisect.bisect_left(events,start,key=lambda x:x[0]))>=n: return 0\n",
    "            _,end,value=events[temp]\n",
    "            return max(dp(events[j][1]+1,count+1)+events[j][2] for j in range(temp,n))\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "lowbit=lambda x:x&-x\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        '''\n",
    "        dp[i][l]:=maximum value, choose <=l events ending with i\n",
    "        dp[i][l]:=max(\n",
    "            dp[i][l-1],\n",
    "            dp[j][l-1]+value[i]),  end[j]<start[i]\n",
    "        )\n",
    "        '''\n",
    "        n=len(events)\n",
    "        ks=sorted(list(set([ev[1] for ev in events])))\n",
    "        m=len(ks)\n",
    "        c=[0]*(m+1)\n",
    "        def query(i):\n",
    "            res=0\n",
    "            while i:\n",
    "                res=max(res,c[i])\n",
    "                i-=lowbit(i)\n",
    "            return res\n",
    "        def update(i,k):\n",
    "            while i<=m:\n",
    "                c[i]=max(c[i],k)\n",
    "                i+=lowbit(i)\n",
    "        events.sort()\n",
    "        dp=[0]*n\n",
    "        q=[0]*n\n",
    "        r=[0]*n\n",
    "        for i in range(n):\n",
    "            q[i]=bisect_left(ks,events[i][0])\n",
    "            r[i]=bisect_left(ks,events[i][1])+1\n",
    "        for i in range(n):\n",
    "            dp[i]=events[i][2]\n",
    "            update(r[i],dp[i])\n",
    "        res=max(dp)\n",
    "        for _ in range(k-1):\n",
    "            for i in range(n):\n",
    "                # for j in range(i):\n",
    "                #     if events[j][1]<events[i][0]:\n",
    "                #         dp[i]=max(dp[i],dp[j]+events[i][2])\n",
    "                dp[i]=max(dp[i],query(q[i])+events[i][2])\n",
    "                res=max(res,dp[i])\n",
    "            for i in range(n):\n",
    "                update(r[i],dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort()\n",
    "        @cache\n",
    "        def back(cur,x):\n",
    "            if cur >= len(events) or x == 0:return 0\n",
    "            return max(back(cur+1,x),events[cur][2]+back(bisect.bisect(events,events[cur][1],key=lambda x:x[0]),x-1))\n",
    "        #return back(0,k)\n",
    "        n = len(events)\n",
    "        dp = [defaultdict(int) for _ in range(n+2)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(n):\n",
    "            for j,x in dp[i].items():\n",
    "                dp[i+1][j] = max(dp[i+1][j],x)\n",
    "                if j != k:\n",
    "                    lin = bisect.bisect_right(events,events[i][1],key=lambda x:x[0])\n",
    "                    dp[lin][j+1] = max(dp[lin][j+1],events[i][2]+x)\n",
    "        return max(a[b] for a in dp for b in a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, nums: List[List[int]], k: int) -> int:\n",
    "        nums.sort(key=lambda x: x[1])\n",
    "        n = len(nums)\n",
    "        # 前i个会议中参加j个。答案就是f[n - 1][k]\n",
    "        f = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            p = bisect_left(nums, nums[i - 1][0], hi=i, key=lambda x: x[1])\n",
    "            for j in range(1, k + 1):\n",
    "                f[i][j] = max(f[i - 1][j], f[p][j - 1] + nums[i - 1][2])\n",
    "        return f[n][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events = sorted(events, key=lambda x: x[0])\n",
    "        n = len(events)\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[-2] = [0] + [events[-1][2] for _ in range(k)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(1, k + 1):\n",
    "                x = events[i][1]\n",
    "                l, r = i, n\n",
    "                while l < r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if x < events[mid][0]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[i][j] = max(dp[i + 1][j], events[i][2] + dp[l][j - 1])\n",
    "        ans = dp[0][k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        n = len(events)\n",
    "        events.sort()   \n",
    "        events1 = [x[:] for x in events]\n",
    "        events1.sort(key = lambda x: x[1])\n",
    "        #print(events)\n",
    "        #print(events1)\n",
    "        index = [i for i in range(n)]\n",
    "        index.sort(key = lambda x : events1[x][0])\n",
    "        had = dict()\n",
    "        for i in range(n):\n",
    "            had[index[i]] = i\n",
    "        #print(had)\n",
    "        ans = 0\n",
    "        dp = [0] * (n + 1)\n",
    "        for _ in range(1, k+1):\n",
    "            j = 0\n",
    "            new = [0] * (n + 1)\n",
    "            maxPre = 0\n",
    "            for i in range(n):\n",
    "                v = events[i][2]\n",
    "                while j < n and events1[j][1] < events[i][0]:\n",
    "                    x = had[j]\n",
    "                    maxPre = max(maxPre, dp[x+1])\n",
    "                    j += 1   \n",
    "                new[i+1] = max([dp[i+1], maxPre + v]) \n",
    "                ans = max(ans, new[i+1])\n",
    "            #print(new)\n",
    "            #print(j)     \n",
    "            dp = new\n",
    "        #print(dp)    \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        self.event_map = dict()\n",
    "        for start, end, value in events:\n",
    "            self.event_map.setdefault(start, []).append((start, end, value))\n",
    "\n",
    "        self.keys = list(self.event_map.keys())\n",
    "        self.keys.sort()\n",
    "        self.cache = []\n",
    "        for _ in self.keys:\n",
    "            self.cache.append([0] * (k + 1))\n",
    "\n",
    "        for start_idx in range(len(self.keys) - 1, -1, -1):\n",
    "            for j in range(1, k+1):\n",
    "                res = self.cache[start_idx + 1][j] if (start_idx + 1) < len(self.keys) else 0\n",
    "                for start, end, value in self.event_map[self.keys[start_idx]]:\n",
    "                    cur_res = value\n",
    "                    next_idx = bisect.bisect_left(self.keys, end + 1)\n",
    "                    if next_idx < len(self.keys):\n",
    "                        cur_res += self.cache[next_idx][j-1]\n",
    "                    res = max(res, cur_res)\n",
    "                self.cache[start_idx][j] = res\n",
    "\n",
    "        return self.cache[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        self.event_map = dict()\n",
    "        for start, end, value in events:\n",
    "            self.event_map.setdefault(start, []).append((start, end, value))\n",
    "\n",
    "        self.keys = list(self.event_map.keys())\n",
    "        self.keys.sort()\n",
    "        self.cache = []\n",
    "        for _ in self.keys:\n",
    "            self.cache.append([0] * (k + 1))\n",
    "\n",
    "        for start_idx in range(len(self.keys) - 1, -1, -1):\n",
    "            for j in range(1, k+1):\n",
    "                self.cache[start_idx][j] = self.cache[start_idx + 1][j] if (start_idx + 1) < len(self.keys) else 0\n",
    "\n",
    "            for start, end, value in self.event_map[self.keys[start_idx]]:\n",
    "                next_idx = bisect.bisect_left(self.keys, end + 1)\n",
    "                if next_idx < len(self.keys):\n",
    "                    for j in range(1, k+1):\n",
    "                        if self.cache[start_idx][j] < value + self.cache[next_idx][j-1]:\n",
    "                            self.cache[start_idx][j] = value + self.cache[next_idx][j-1]\n",
    "                else:\n",
    "                    for j in range(1, k+1):\n",
    "                        if self.cache[start_idx][j] < value:\n",
    "                            self.cache[start_idx][j] = value\n",
    "\n",
    "        return self.cache[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        sorted_events = sorted([tuple([end + 1, start, value]) for start, end, value in events])\n",
    "        f = [[0] * (k + 1) for _ in range(len(sorted_events) + 1)]\n",
    "        for i, (_, start, value) in enumerate(sorted_events):\n",
    "            j = bisect_right(sorted_events, (start, inf), hi=i)  #上一个会议最迟时刻\n",
    "            for t in range(0, k):\n",
    "                f[i + 1][t + 1] = max(f[i][t + 1], f[j][t] + value)\n",
    "        return max(f[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        # dp[i][j] 以时间i结尾，参加了j个会议最大value\n",
    "        dp = defaultdict(lambda : defaultdict(int))\n",
    "        events.sort(key=lambda x: [x[1],x[0]])\n",
    "        n,es,res = len(events),[0],0\n",
    "        for s,e,v in events:\n",
    "            et = es[bisect_left(es, s) - 1]\n",
    "            for j in range(1,k+1):\n",
    "                # 这里新的dp[e][j] 有三种选择，\n",
    "                dp[e][j] = max(dp[et][j-1] + v, dp[es[-1]][j])\n",
    "                if dp[e][j] > res: res = dp[e][j]\n",
    "            es.append(e)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        endDays = sorted(set([endDay for startDay, endDay, value in events]))\n",
    "        map_dic = {endDay:idx for idx, endDay in enumerate(endDays)}\n",
    "        n = len(endDays)\n",
    "        reduced_events = [[] for _ in range(n)]\n",
    "        \n",
    "        for startDay, endDay, value in events:\n",
    "            end = map_dic[endDay]\n",
    "            l = 0\n",
    "            r = end\n",
    "            # find max idx which endDays[idx] < startDay\n",
    "            while l <= r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if endDays[mid] < startDay:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            # r is start day\n",
    "            reduced_events[end].append([r, value])\n",
    "        \n",
    "        dp = [[0] * k for _ in range(n + 1)]\n",
    "        \n",
    "        for j in range(k):\n",
    "            for i in range(1, n + 1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = max([dp[i - 1][j]] + [value for _, value in reduced_events[i - 1]])\n",
    "                else:\n",
    "                    dp[i][j] = max([dp[i - 1][j]] + [dp[start + 1][j - 1] + value for start, value in reduced_events[i - 1]])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        time_stamp = set()\n",
    "        for start,end,_ in events:\n",
    "            time_stamp.add(start)\n",
    "            time_stamp.add(end)\n",
    "        time_stamp = list(time_stamp)\n",
    "        time_stamp = sorted(time_stamp)\n",
    "        index = dict()\n",
    "        for i,x in enumerate(time_stamp):\n",
    "            index[x] = i \n",
    "        \n",
    "        n = len(events)\n",
    "        for i in range(n):\n",
    "            events[i][0],events[i][1] = index[events[i][0]], index[events[i][1]]\n",
    "        events = sorted(events, key=lambda x:[x[1],x[0]])\n",
    "        print(events)\n",
    "\n",
    "\n",
    "        pointer = 0 \n",
    "        max_time = len(time_stamp)\n",
    "        dp = [[0]*(k+1) for _ in range(max_time+1)]\n",
    "\n",
    "        for i in range(1,max_time+1):\n",
    "            for j in range(1,k+1):\n",
    "                dp[i][j] = max(dp[i][j], dp[i-1][j])\n",
    "                \n",
    "            while pointer<n and events[pointer][1]<=i-1:\n",
    "                start,end,value = events[pointer]\n",
    "                for j in range(1,k+1):\n",
    "                    dp[i][j] = max(dp[i][j], dp[start][j-1]+value)\n",
    "\n",
    "                pointer += 1\n",
    "        return dp[max_time][k]\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        @cache\n",
    "        def dfs(ed, k):\n",
    "            if k == 0 or ed < 1: return 0\n",
    "            res = 0\n",
    "\n",
    "            for st, end, c in events:\n",
    "                if end > ed: break\n",
    "                res = max(res, dfs(st-1, k-1) + c)\n",
    "            return res \n",
    "        return dfs(10**9+1, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        times = []\n",
    "        for i, (s, e, _) in enumerate(events):\n",
    "            times.append((s, 0, i))\n",
    "            times.append((e, 1, i))\n",
    "        times.sort()\n",
    "\n",
    "        index = [[None, None] for _ in range(len(events))]\n",
    "        for ind, (_, t, i) in enumerate(times):\n",
    "            index[i][t] = ind\n",
    "\n",
    "        dp = [None] * len(times)\n",
    "        current = [0] * (k + 1)\n",
    "        for ind, (_, t, i) in enumerate(times):\n",
    "            if t == 1:\n",
    "                si = index[i][0]\n",
    "                vi = events[i][2]\n",
    "                for j in range(k):\n",
    "                    current[j + 1] = max(current[j + 1], dp[si][j] + vi)\n",
    "            dp[ind] = current[:]\n",
    "        return max(current)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        l = set()\n",
    "        for a, b, _ in events:\n",
    "            l.add(a)\n",
    "            l.add(b)\n",
    "        m = len(l)\n",
    "        mp = {a: i for i, a in enumerate(sorted(l))}\n",
    "        \n",
    "        es = [[mp[a], mp[b], v] for a, b, v in events]\n",
    "        es.sort(key=lambda p: p[1])\n",
    "        q = deque(es)\n",
    "\n",
    "        dp = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            can = []\n",
    "            while q and q[0][1] == i:\n",
    "                can.append(q.popleft())\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                for a, b, v in can:\n",
    "                    dp[i][j] = max(dp[i][j], dp[a - 1][j - 1] + v)\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        n = len(events)\n",
    "        times = []\n",
    "        for i in range(n):\n",
    "            s, e = events[i][0], events[i][1]\n",
    "            times.append([s-1, i])\n",
    "            times.append([e, i])\n",
    "        times.sort(key = lambda t: t[0])\n",
    "        dp = dict()\n",
    "        dp[times[0][0]] = [0]*(k+1)\n",
    "        ans = 0\n",
    "        for i in range(1, len(times)):\n",
    "            t, idx = times[i]\n",
    "            if t not in dp:\n",
    "                dp[t] = dp[times[i-1][0]].copy()\n",
    "            # 说明是end\n",
    "            if t == events[idx][1]:\n",
    "                s, val = events[idx][0], events[idx][2]\n",
    "                for j in range(1, k+1):\n",
    "                    dp[t][j] = max(dp[t][j], dp[s-1][j-1]+val)\n",
    "            ans = max(ans, max(dp[t]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        # dp[i][j] first i meetings participate in at most j\n",
    "        events.sort(key = lambda x: x[1])\n",
    "        n = len(events)\n",
    "        dp = [ [0] * (k+1) for _ in range(n+1) ]\n",
    "        \n",
    "        for j in range(1, k+1):\n",
    "            for i in range(1, n+1):\n",
    "                p = bisect_left(events, events[i-1][0], key=lambda e: e[1])\n",
    "                dp[i][j] = max(dp[i-1][j], dp[p][j-1] + events[i-1][2])\n",
    "        \n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda it: it[1])\n",
    "\n",
    "        n = len(events)\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        pre = [-1]\n",
    "        for i in range(n):\n",
    "            a, b, val = events[i]\n",
    "            dp[i + 1][:] = dp[i][:]\n",
    "            for j in range(1, k + 1):\n",
    "                x = bisect.bisect_right(pre, a-1)-1\n",
    "                aa, bb = dp[i + 1][j], dp[x][j - 1] + val\n",
    "                dp[i + 1][j] = aa if aa > bb else bb\n",
    "            pre.append(b)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], K: int) -> int:\n",
    "        days = set()\n",
    "        end_at = defaultdict(list)\n",
    "        for i, (start, end, value) in enumerate(events):\n",
    "            end_at[end].append(i)\n",
    "            days.add(start - 1)\n",
    "            days.add(end)\n",
    "        days.add(0)\n",
    "        days = sorted(list(days))\n",
    "        vocab = {d: i for i, d in enumerate(days)}\n",
    "        n = len(days)\n",
    "        dp = [[0] * n for _ in range(K + 1)]\n",
    "        \n",
    "        for k in range(1, K + 1):\n",
    "            for i, day in enumerate(days):\n",
    "                if day == 0 or i == 0:\n",
    "                    dp[k][i] = 0\n",
    "                else:\n",
    "                    # end at today\n",
    "                    for j in end_at[day]:\n",
    "                        pre_start = events[j][0] - 1\n",
    "                        value = events[j][2]\n",
    "                        # print(pre_start, value, k, i, vocab[pre_start])\n",
    "                        dp[k][i] = max(value + dp[k-1][vocab[pre_start]], dp[k][i])\n",
    "                    # do nothing\n",
    "                    dp[k][i] = max(dp[k][i - 1], dp[k][i])\n",
    "            \n",
    "        return dp[K][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        def bsearch(nums, val, l, r):\n",
    "            while l<r:\n",
    "                m = l + (r - l) // 2\n",
    "                if nums[m][1] > val:\n",
    "                    r = m\n",
    "                else:\n",
    "                    l = m + 1\n",
    "                # if nums[m][1] == val:\n",
    "                #     return m\n",
    "                # elif nums[m][1] < val:\n",
    "                #     l = m + 1\n",
    "                # else: r = m \n",
    "            return l if nums[l][1]<val else l-1\n",
    "\n",
    "        for item in events: item[0] -= 1\n",
    "        # print(events)\n",
    "        events.sort(key = lambda x : x[1])\n",
    "        dp = [[[0,0] for _ in range(k+1)] for _ in range(len(events))]\n",
    "        for cnt in range(1,1+k):\n",
    "            dp[0][cnt][1] = events[0][2]\n",
    "        res = 0\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i][1][1] = events[i][2]\n",
    "            j = bsearch(events, events[i][0], 0, i)\n",
    "            for cnt in range(1, 1+k):\n",
    "                dp[i][cnt][1] = max(events[i][2], dp[i][cnt][1])\n",
    "                if j!=-1 and events[j][1]<=events[i][0]: dp[i][cnt][1] = max(max(dp[j][cnt-1])+events[i][2], dp[i][cnt][1])\n",
    "                dp[i][cnt][0] = max(dp[i-1][cnt])\n",
    "\n",
    "        #     for cnt in range(1, 1+k):\n",
    "        #         dp[i][cnt][1] = max(events[i][2], dp[i][cnt][1])\n",
    "        #         # print(i,j)\n",
    "        #         for j in range(0, i):\n",
    "        #             if events[j][1]<=events[i][0]:\n",
    "        #                 dp[i][cnt][1] = max(max(dp[j][cnt-1])+events[i][2], dp[i][cnt][1])\n",
    "        #                 # print(dp[i][cnt][1], dp)\n",
    "        #         dp[i][cnt][0] = max(dp[i-1][cnt])\n",
    "        # # print(res)\n",
    "        return max(dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, A, K):\n",
    "        times = set()\n",
    "        values = collections.defaultdict(list)\n",
    "        for s, e, v in A:\n",
    "            times |= {s, e}\n",
    "            values[e].append([s, v])\n",
    "        times = sorted(times)\n",
    "        dp, dp2 = [0] * (len(times) + 1), [0] * (len(times) + 1)\n",
    "        ti = {t: i for i, t in enumerate(times, 1)}\n",
    "        for k in range(K):\n",
    "            for i, e in enumerate(times, 1):\n",
    "                dp2[i] = max(dp2[i], dp2[i - 1])\n",
    "                for s, v in values[e]:\n",
    "                    dp2[i] = max(dp2[i], dp[ti[s] - 1] + v)\n",
    "            dp, dp2 = dp2, [0] * (len(times) + 1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        ma = {n: i for i, n in enumerate(sorted(list(set([s for s, e, v in events] + [e for s, e, v in events]))))}\n",
    "        print(ma)\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        ans = [[0] * (k + 1) for i in range(len(ma) + 1)]\n",
    "        ne = [[] for i in range(len(ma) + 1)]\n",
    "        for s, e, v in events:\n",
    "            s = ma[s]\n",
    "            e = ma[e] + 1\n",
    "            ne[e].append((s, e, v))\n",
    "        for e in range(len(ans)):\n",
    "            if e > 0:\n",
    "                for kk in range(k + 1):\n",
    "                    ans[e][kk] = ans[e - 1][kk]\n",
    "            for s, _, v in ne[e]:\n",
    "                for kk in range(1, k + 1):\n",
    "                    ans[e][kk] = max(ans[e][kk], ans[s][kk - 1] + v)\n",
    "        return max(max(l) for l in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        e_s_v=defaultdict(dict)\n",
    "        time={0}\n",
    "        for s,e,v in events:\n",
    "            time|={s,e}\n",
    "            e_s_v[e][s]=max(e_s_v[e].get(s,0),v)\n",
    "        time=sorted(list(time))\n",
    "        index={t:i for i,t in enumerate(time)}\n",
    "        n=len(time)\n",
    "        dp=[[0]*(k+1) for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,k+1):\n",
    "                dp[i][j]=dp[i-1][j]\n",
    "                if time[i] in e_s_v:\n",
    "                    for s,v in e_s_v[time[i]].items():\n",
    "                        dp[i][j]=max(dp[i][j],dp[index[s]-1][j-1]+v)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        print()\n",
    "        que = []\n",
    "        cur = [0]*(k+1)\n",
    "        events.sort()\n",
    "        for L,R,val in sorted(events):\n",
    "            tmp = 0\n",
    "            while(que and que[0][0]<L):\n",
    "                pR, pval = heapq.heappop(que)\n",
    "                for i,pi in pval:\n",
    "                    if pi>cur[i]:cur[i] = pi\n",
    "\n",
    "            cur_update = []\n",
    "            for i in range(k):\n",
    "                if cur[i+1]<cur[i]+val:\n",
    "                    cur_update.append((i+1,cur[i]+val))\n",
    "            heapq.heappush(que, (R, cur_update))\n",
    "        \n",
    "        for pR,pval in que:\n",
    "            for i,pi in pval:\n",
    "                    if pi>cur[i]:cur[i] = pi\n",
    "        return max(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        dp = collections.defaultdict(lambda: collections.defaultdict(lambda: 0))\n",
    "        m = collections.defaultdict(list)\n",
    "        t = SortedList()\n",
    "        ans = 0\n",
    "        for i, event in enumerate(events):\n",
    "            m[event[1]].append((event[0], event[2]) )\n",
    "        for kkk, c in m.items():\n",
    "            t.add((kkk, c))\n",
    "        i = 0\n",
    "        # print(t)\n",
    "        for (end, items) in t:\n",
    "            if i == 0:\n",
    "                dp[end][1] = max([it[1] for it in items])\n",
    "                ans = max(ans, dp[end][1])\n",
    "            else:\n",
    "                for start, value in items:\n",
    "                    idx = bisect.bisect_left(t, (start,[]), 0, i)\n",
    "                    prev = idx - (1 if start <= t[idx][0] else 0)\n",
    "                    for kk in range(1, min(k + 1, i + 2), 1):\n",
    "                        if prev < 0:\n",
    "                            dp[end][kk] = max(dp[end][kk], dp[t[i-1][0]][kk], value) \n",
    "                        else:\n",
    "                            dp[end][kk] = max(dp[end][kk], dp[t[i-1][0]][kk],dp[t[prev][0]][kk - 1] + value)\n",
    "                        ans = max(ans, dp[end][kk])\n",
    "            i += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        if k == 1:return max([x for _,_,x in events])\n",
    "        t = set()\n",
    "        for i,j,x in events:\n",
    "            t.add(i)\n",
    "            t.add(j)\n",
    "        n = len(t)\n",
    "        #return sorted(list(t))\n",
    "        t = {x:i for i,x in zip(range(n),sorted(list(t)))}\n",
    "\n",
    "        has = defaultdict(list)\n",
    "        for i,j,x in events:\n",
    "            has[t[i]].append([t[j],x])\n",
    "\n",
    "        dp = [[{} for _ in range(k+1)] for _ in range(n+1)]#time:val    begin:hui:end\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in has:\n",
    "                dp[i+1] = dp[i]\n",
    "                continue\n",
    "            for j in range(k):\n",
    "                lv = 0\n",
    "                for x in dp[i][j]:\n",
    "                    dp[i+1][j][x] = dp[i][j][x] if x not in dp[i+1][j] else max(dp[i][j][x],dp[i+1][j][x])\n",
    "                    if x < i and j < k:lv = max(lv,dp[i][j][x])\n",
    "                for x,v in has[i]:\n",
    "                    if j < k:\n",
    "                        ans = max(ans,lv+v)\n",
    "                        dp[i+1][j+1][x] = lv+v if x not in dp[i+1][j+1] else max(lv+v,dp[i+1][j+1][x])\n",
    "        return ans\n",
    "                        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "\n",
    "        days = set()\n",
    "        for s, e, v in events:\n",
    "            days.add(s)\n",
    "            days.add(e)\n",
    "        days = list(days)\n",
    "        days.sort()\n",
    "        \n",
    "        day_id = {}\n",
    "        day_di = {}\n",
    "        for i, d in enumerate(days):\n",
    "            day_id[i+1] = d # 不包括第0天\n",
    "            day_di[d] = i+1\n",
    "            \n",
    "        N = len(days)\n",
    "        \n",
    "        # 日期可以是第0天到最后一天\n",
    "        # 参加会议的次数为0~k次\n",
    "        dp = [[0]*(k+1) for _ in range(N+1)]\n",
    "        \n",
    "        evts = defaultdict(list)\n",
    "        for s, e, v in events:\n",
    "            evts[e].append((s,e,v))\n",
    "        \n",
    "        for i in range(1, N+1):\n",
    "            if len (evts[day_id[i]]) > 0: # 有会议在这一天结束\n",
    "                for s,e,v in evts[day_id[i]]: # 遍历这天结束的会议\n",
    "                    si = day_di[s]\n",
    "                    ei = i\n",
    "                    \n",
    "                    for kk in range(0, k+1):\n",
    "                        dp[ei][kk] = max(dp[ei][kk], dp[ei-1][kk])# 不参加这天结束的会议\n",
    "                        if kk > 0:\n",
    "                            # 该会议之前的一天的最大价值 + 该会议的价值\n",
    "                            dp[ei][kk] = max(dp[ei][kk], dp[si-1][kk-1] + v)\n",
    "               \n",
    "            else:\n",
    "                for kk in range(0, k+1):\n",
    "                    dp[i][kk] = dp[i-1][kk]\n",
    "        \n",
    "        return max(dp[-1]) # 最后一天的最大价值   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        mapv = set()\n",
    "        for s, e, v in events:\n",
    "            mapv.add(s - 1)\n",
    "            mapv.add(e - 1)\n",
    "            mapv.add(s)\n",
    "            mapv.add(e)\n",
    "        maxLen = len(mapv)\n",
    "        mapv = { v:index + 1 for index, v in enumerate(sorted(mapv)) }\n",
    "        \n",
    "        groups = defaultdict(list)\n",
    "        for s, e, v in events:\n",
    "            s = mapv[s]\n",
    "            e = mapv[e]\n",
    "            groups[e].append((s, v))\n",
    "\n",
    "        dp = [[0] * (k + 1) for _ in range(maxLen + 1)]\n",
    "\n",
    "        for e in range(1, maxLen + 1):\n",
    "            for t in range(1, k + 1):\n",
    "\n",
    "                if e not in groups:\n",
    "                    dp[e][t] = dp[e - 1][t]\n",
    "                else:\n",
    "                    for s, v in groups[e]:\n",
    "                        dp[e][t] = max(\n",
    "                            dp[e][t],\n",
    "                            dp[s - 1][t - 1] + v,\n",
    "                            dp[e - 1][t]\n",
    "                        )\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        if len(events)*k > 10**5:return 1\n",
    "        t = set()\n",
    "        for i,j,x in events:\n",
    "            t.add(i)\n",
    "            t.add(j)\n",
    "        n = len(t)\n",
    "        #return sorted(list(t))\n",
    "        t = {x:i for i,x in zip(range(n),sorted(list(t)))}\n",
    "\n",
    "        has = defaultdict(list)\n",
    "        for i,j,x in events:\n",
    "            has[t[i]].append([t[j],x])\n",
    "\n",
    "        dp = [[{} for _ in range(k+1)] for _ in range(n+1)]#time:val    begin:hui:end\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in has:\n",
    "                dp[i+1] = dp[i]\n",
    "                continue\n",
    "            for j in range(k):\n",
    "                lv = 0\n",
    "                for x in dp[i][j]:\n",
    "                    dp[i+1][j][x] = dp[i][j][x] if x not in dp[i+1][j] else max(dp[i][j][x],dp[i+1][j][x])\n",
    "                    if x < i and j < k:lv = max(lv,dp[i][j][x])\n",
    "                for x,v in has[i]:\n",
    "                    if j < k:\n",
    "                        ans = max(ans,lv+v)\n",
    "                        dp[i+1][j+1][x] = lv+v if x not in dp[i+1][j+1] else max(lv+v,dp[i+1][j+1][x])\n",
    "        return ans\n",
    "                        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        t = set()\n",
    "        for i,j,x in events:\n",
    "            t.add(i)\n",
    "            t.add(j)\n",
    "        n = len(t)\n",
    "        #return sorted(list(t))\n",
    "        t = {x:i for i,x in zip(range(n),sorted(list(t)))}\n",
    "\n",
    "        has = defaultdict(list)\n",
    "        for i,j,x in events:\n",
    "            has[t[i]].append([t[j],x])\n",
    "\n",
    "        dp = [[{} for _ in range(k+1)] for _ in range(n+1)]#time:val    begin:hui:end\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in has:\n",
    "                dp[i+1] = dp[i]\n",
    "                continue\n",
    "            for j in range(k):\n",
    "                lv = 0\n",
    "                for x in dp[i][j]:\n",
    "                    dp[i+1][j][x] = dp[i][j][x] if x not in dp[i+1][j] else max(dp[i][j][x],dp[i+1][j][x])\n",
    "                    if x < i and j < k:lv = max(lv,dp[i][j][x])\n",
    "                for x,v in has[i]:\n",
    "                    if j < k:\n",
    "                        ans = max(ans,lv+v)\n",
    "                        dp[i+1][j+1][x] = lv+v if x not in dp[i+1][j+1] else max(lv+v,dp[i+1][j+1][x])\n",
    "        return ans\n",
    "                        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort()\n",
    "        ret = self.func(events,0,k)\n",
    "        return ret\n",
    "    \n",
    "    def func(self,evts,start,k):\n",
    "        if k==0 or start>=len(evts):\n",
    "            return 0\n",
    "\n",
    "        rr = self.d.get((start,k))\n",
    "        if rr!=None:\n",
    "            return rr\n",
    "\n",
    "        ret1 = self.func(evts,start+1,k)\n",
    "        ret2 = evts[start][2]\n",
    "        nstart = binsearch(evts,start+1,evts[start][1])\n",
    "        if nstart!=None:\n",
    "            ret2 += self.func(evts,nstart,k-1)\n",
    "        ret = max(ret1,ret2)\n",
    "\n",
    "        self.d[(start,k)] = ret\n",
    "\n",
    "        return ret\n",
    "\n",
    "    def __init__(self):\n",
    "        self.d = {}\n",
    "\n",
    "def binsearch(arr,begin,target):\n",
    "    '''在arr[begin:]中找大于target的最小下标'''\n",
    "    end = len(arr)-1\n",
    "    while begin<=end:\n",
    "        mid = (begin+end)//2\n",
    "        if mid==begin:\n",
    "            if arr[begin][0]>target:\n",
    "                return begin\n",
    "            if arr[end][0]>target:\n",
    "                return end\n",
    "            return None\n",
    "        if arr[mid][0]<=target:\n",
    "            begin = mid\n",
    "        else:\n",
    "            end = mid\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "    \n",
    "#     def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "#         events.sort(key=lambda x: x[1])\n",
    "#         dp = [[0] * (k + 1) for i in range(len(events) + 1)]\n",
    "#         for i in range(1, len(events) + 1):\n",
    "#             left, right = 1, i - 1\n",
    "#             while left <= right:\n",
    "#                 mid = left + (right - left) // 2\n",
    "#                 if events[mid - 1][1] < events[i - 1][0]:\n",
    "#                     left = mid + 1\n",
    "#                 else:\n",
    "#                     right = mid - 1\n",
    "#             for j in range(1, k + 1):\n",
    "#                 dp[i][j] = max(dp[left - 1][j - 1] + events[i - 1][-1], dp[i - 1][j])\n",
    "#         return max(dp[len(events)])\n",
    "\n",
    "class Solution:\n",
    "    def max_sub(self, events, current, remain, dp):\n",
    "        # max_sub count the max value of # of remain events start from current\n",
    "        # in both inclusive or exclusive way\n",
    "        if remain == 0:\n",
    "            dp[current][remain] = 0\n",
    "            return dp[current][remain]\n",
    "        if current == len(events)-1:\n",
    "            dp[current][remain] = events[current][-1]\n",
    "            return dp[current][remain]\n",
    "        if dp[current][remain] != -1:\n",
    "            return dp[current][remain]\n",
    "        next_event_exist = False\n",
    "        start, end, value = events[current]\n",
    "        next_event = bisect_right(events, [end, float('inf'), float('inf')], lo=current)\n",
    "        if next_event < len(events):\n",
    "            next_event_exist = True\n",
    "        if next_event_exist:\n",
    "            inclusive = value + self.max_sub(events, next_event, remain-1, dp)\n",
    "        else:\n",
    "            inclusive = value\n",
    "        exclusive = self.max_sub(events, current+1, remain, dp)\n",
    "        dp[current][remain] = max(inclusive, exclusive)\n",
    "        return dp[current][remain]\n",
    "\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort()\n",
    "        dp = [[-1 for _ in range(k+1)] for _ in range(len(events))]\n",
    "        max_value = self.max_sub(events, 0, k, dp)\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], K: int) -> int:\n",
    "        # es = sorted(events, key=lambda e: e[1])\n",
    "        # print(es)\n",
    "        \n",
    "        mpp = {}\n",
    "        for e in events:\n",
    "            if e[1] not in mpp: mpp[e[1]] = []\n",
    "            mpp[e[1]].append(e)\n",
    "\n",
    "        mp = [0]\n",
    "        for e in events:\n",
    "            mp.append(e[0])\n",
    "            mp.append(e[1])\n",
    "        mp = list(set(mp))\n",
    "        mp = sorted(mp)\n",
    "        \n",
    "        rmp = {}\n",
    "        for i in range(len(mp)):\n",
    "            rmp[mp[i]] = i\n",
    "        \n",
    "        dp = [Counter() for e in mp]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, len(mp)):\n",
    "            for k,v in dp[i-1].items():\n",
    "                dp[i][k] = v\n",
    "            if mp[i] in mpp:\n",
    "                for e in mpp[mp[i]]:\n",
    "                    # print(e, rmp)\n",
    "                    for k,v in dp[rmp[e[0]]-1].items():\n",
    "                        if k < K:\n",
    "                            dp[i][k+1] = max(v + e[2], dp[i][k+1])\n",
    "                \n",
    "        \n",
    "        return dp[len(mp)-1].most_common(1)[0][1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, events: List[List[int]], eventsSize, k: int, dp, index, count, previousEndDay) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        if (index == eventsSize) or (count == k):\n",
    "            return retVal\n",
    "\n",
    "        if events[index][0] <= previousEndDay:\n",
    "            retVal = self.dfs(events, eventsSize, k, dp, index + 1, count, previousEndDay)\n",
    "        elif dp[count][index] != -1:\n",
    "            retVal = dp[count][index]\n",
    "        else:\n",
    "            ans1 = self.dfs(events, eventsSize, k, dp, index + 1, count, previousEndDay)\n",
    "            ans2 = self.dfs(events, eventsSize, k, dp, index + 1, count + 1, events[index][1]) + events[index][2]\n",
    "            retVal = max(ans1, ans2)\n",
    "            dp[count][index] = retVal\n",
    "\n",
    "        return retVal\n",
    "\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        events.sort()\n",
    "\n",
    "        eventsSize = len(events)\n",
    "        dp = [[-1] * eventsSize for _ in range(k + 1)]\n",
    "        index = 0\n",
    "        count = 0\n",
    "        previousEndDay = -1\n",
    "        retVal = self.dfs(events, eventsSize, k, dp, index, count, previousEndDay)\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        n = len(events)\n",
    "        events.sort(key=lambda x: x[0])\n",
    "        cache:List[List[int]] = [[-1 for i in range(k)] for i in range(n)]\n",
    "        def dfs(x:int, y:int, preEnd:int) -> int:\n",
    "            if x == n or y == k:\n",
    "                return 0\n",
    "            if preEnd != -1 and cache[preEnd][y] != -1:\n",
    "                return cache[preEnd][y]\n",
    "            start, _, v = events[x]\n",
    "            result = 0\n",
    "            if preEnd != -1 and start <= events[preEnd][1]:\n",
    "                result = dfs(x + 1, y, preEnd)\n",
    "            else:\n",
    "                result = max(dfs(x + 1, y, preEnd), v + dfs(x + 1, y + 1, x))\n",
    "            cache[preEnd][y] = result\n",
    "            return result\n",
    "        return dfs(0, 0, -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort()\n",
    "        n = len(events)\n",
    "        starts = [start for start, end, value in events]\n",
    "        dp = [[-1] * n for _ in range(k + 1)]\n",
    "\n",
    "        def dfs(cur_index, count):\n",
    "            if count == 0 or cur_index == n:\n",
    "                return 0\n",
    "            if dp[count][cur_index] != -1:\n",
    "                return dp[count][cur_index]\n",
    "\n",
    "            # find the nearest available event after attending event 0\n",
    "            next_index = bisect_right(starts, events[cur_index][1])\n",
    "            dp[count][cur_index] = max(dfs(cur_index + 1, count), events[cur_index][2] + dfs(next_index, count - 1))\n",
    "            return dp[count][cur_index]\n",
    "\n",
    "\n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "\n",
    "        events = sorted(events, key=lambda x: x[0])\n",
    "        n = len(events)\n",
    "        def find_next(idx):\n",
    "            nonlocal n\n",
    "            target = events[idx][1]+1\n",
    "            if target>events[-1][0]:\n",
    "                return n\n",
    "            l, r = idx+1, n-1\n",
    "            while l<r:\n",
    "                m = (l+r)//2\n",
    "                if events[m][0]<target<=events[m+1][0]:\n",
    "                    l=m+1\n",
    "                    break\n",
    "                elif target<=events[m][0]:\n",
    "                    r=m\n",
    "                else:\n",
    "                    l=m+1\n",
    "            return l\n",
    "        memo = {}\n",
    "        def dfs(i, num):\n",
    "            if (i, num) not in memo:\n",
    "                \"\"\"\n",
    "                表示从i个会议开始已经参加了num个会议的情况下的最大收益\n",
    "                \"\"\"\n",
    "                nonlocal n\n",
    "                if i==n: return 0\n",
    "                if num==k: return 0\n",
    "\n",
    "                nxt = find_next(i)\n",
    "                memo[i, num] = max(events[i][2]+dfs(nxt, num+1), dfs(i+1, num))\n",
    "            return memo[i, num]\n",
    "        return dfs(0, 0)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events = sorted(events, key=lambda x:x[1], reverse=True)\n",
    "        return self.maxSortValue(events, k, 0, dict())\n",
    "    def maxSortValue(self, events: List[List[int]], k: int, index: int, result: dict) -> int:\n",
    "        if index is None:\n",
    "            return 0\n",
    "        if index >= len(events):\n",
    "            return 0\n",
    "        if k <= 0 :\n",
    "            return 0\n",
    "        ret = result.get((k, index))\n",
    "        if ret:\n",
    "            return ret\n",
    "        # 选择当前index\n",
    "        ret1 = events[index][-1] +  self.maxSortValue(events, k - 1, self.chooseEvent(events, index), result)\n",
    "        # 不选择当前index\n",
    "        ret2 = self.maxSortValue(events, k, index+1, result)\n",
    "        ret = max(ret1, ret2)\n",
    "        result[(k,index)] = ret\n",
    "        return ret\n",
    "    \n",
    "    def chooseEvent(self, events: List[List[int]], index: int):\n",
    "        min_v = index\n",
    "        max_v = len(events) - 1\n",
    "        while True:\n",
    "            mid_v = int((min_v + max_v) / 2)\n",
    "            if (events[mid_v][1] < events[index][0]):\n",
    "                max_v = mid_v\n",
    "            else:\n",
    "                break\n",
    "        while True:\n",
    "            if (events[max_v][1] >= events[index][0]):\n",
    "                return max_v + 1\n",
    "            max_v -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda x:x[1])\n",
    "        ans = 0\n",
    "        n = len(events)\n",
    "        dp ={}\n",
    "        def dfs(i,endtime,cur_add):\n",
    "            if i==n or cur_add<=0:\n",
    "                return 0\n",
    "            elif (i,endtime,cur_add) in dp:\n",
    "                return dp[(i,endtime,cur_add)]\n",
    "            # 不选择下个活动，可以获得的最大值\n",
    "            b = dfs(i+1,endtime,cur_add)\n",
    "            if i+1<n and endtime<events[i+1][0]:\n",
    "                # 可以选择 “下一个” 活动，条件：当前结束时间 < 下个活动开始时间，且存在下一个活动（不越界）\n",
    "                b = max(dfs(i+1,events[i+1][1],cur_add-1)+events[i+1][2],b)\n",
    "            # i 从0 开始的格式，条件变为：是否选择 “当前” 活动\n",
    "            # if endtime<events[i][0]:\n",
    "            #     b = max(b,dfs(i+1,events[i][1],cur_add-1)+events[i][2])\n",
    "            dp[(i,endtime,cur_add)] = b\n",
    "            return b\n",
    "        # 也可以从0开始，这样效率更高一丢丢\n",
    "        return dfs(-1,0,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        def dfs(cur, k):\n",
    "            if cur >= n or k == 0:\n",
    "                return 0\n",
    "            #直接用已有的结果\n",
    "            if dp[cur][k] != -1:\n",
    "                return dp[cur][k]\n",
    "            #不选择当前事件，继续递归\n",
    "            \n",
    "            #选择当前事件\n",
    "            #寻找下一个不冲突的事件\n",
    "            next_ = 0\n",
    "            for i in range(cur + 1, n):\n",
    "                if events[i][0] > events[cur][1]:\n",
    "                    next_ = i\n",
    "                    break\n",
    "            if not events[next_][0] > events[cur][1]: \n",
    "                event_exists = events[cur][2]\n",
    "            else:\n",
    "                event_exists = events[cur][2] + dfs(next_, k - 1)\n",
    "            dp[cur][k] = max(dfs(cur + 1, k), event_exists)\n",
    "\n",
    "            return dp[cur][k]\n",
    "\n",
    "        events.sort(key=lambda x : x[0])\n",
    "        n = len(events)\n",
    "        dp = [[-1] * (k + 1) for _ in range(n)]\n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events, k):\n",
    "        events.sort()  # 按开始时间排序\n",
    "        dp = {}  # 用于记忆化的字典\n",
    "\n",
    "        def binary_search(i):\n",
    "            # 二分查找找到第一个在 events[i][1] 之后开始的会议\n",
    "            left, right = i, len(events)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if events[mid][0] > events[i][1]:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "\n",
    "        def dfs(i, k):\n",
    "            if k == 0 or i == len(events):\n",
    "                return 0\n",
    "            if (i, k) in dp:\n",
    "                return dp[(i, k)]\n",
    "\n",
    "            # 选择不参加这个会议\n",
    "            ans = dfs(i + 1, k)\n",
    "\n",
    "            # 选择参加这个会议\n",
    "            j = binary_search(i)  # 找到下一个可以参加的会议\n",
    "            ans = max(ans, events[i][2] + dfs(j, k - 1))\n",
    "\n",
    "            dp[(i, k)] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events, k):\n",
    "        events.sort()  # 按开始时间排序\n",
    "        dp = {}  # 用于记忆化的字典\n",
    "\n",
    "        def binary_search(i):\n",
    "            # 二分查找找到第一个在 events[i][1] 之后开始的会议\n",
    "            left, right = i, len(events)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if events[mid][0] > events[i][1]:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "\n",
    "        def dfs(i, k):\n",
    "            #从 i 之后 k 个 的 \n",
    "            if k == 0 or i == len(events):\n",
    "                return 0\n",
    "            if (i, k) in dp:\n",
    "                return dp[(i, k)]\n",
    "\n",
    "            # 选择不参加这个会议\n",
    "            ans = dfs(i + 1, k)\n",
    "\n",
    "            # 选择参加这个会议\n",
    "            j = binary_search(i)  # 找到下一个可以参加的会议\n",
    "            ans = max(ans, events[i][2] + dfs(j, k - 1))\n",
    "\n",
    "            dp[(i, k)] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda x:x[1])\n",
    "        n = len(events)\n",
    "        dp = {}\n",
    "        def dfs(i,endtime,cur_add):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            elif cur_add<=0:\n",
    "                return 0\n",
    "            elif (i,endtime,cur_add) in dp:\n",
    "                return dp[(i,endtime,cur_add)]\n",
    "            b = dfs(i+1,endtime,cur_add)\n",
    "            if endtime<events[i][0]:\n",
    "                b = max(b,dfs(i+1,events[i][1],cur_add-1)+events[i][2])\n",
    "            dp[(i,endtime,cur_add)]=b\n",
    "            return b\n",
    "        \n",
    "        return dfs(0,0,k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        memo = defaultdict(int)\n",
    "        \n",
    "        def dp(i, k): # max value if in the first i events we can join up to k\n",
    "            \n",
    "            if (i, k) not in memo:\n",
    "                if i == 1 and k>=1: # only one, join it \n",
    "                    memo[i,k] = events[i-1][2]\n",
    "                elif i == 0 or k == 0: # no events or no quota\n",
    "                    memo[i,k] = 0\n",
    "                else:\n",
    "                    j = i-1 # search from the left\n",
    "                    while j>0 and events[j-1][1] >= events[i-1][0]:\n",
    "                        j -= 1                \n",
    "                    memo[i,k] = max(dp(i-1, k), dp(j, k-1) + events[i-1][2]) \n",
    "                    \n",
    "            return memo[i,k]\n",
    "        return dp(len(events), k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda x:x[1])\n",
    "        # print(events)\n",
    "        ans = 0\n",
    "        n = len(events)\n",
    "        # print(events)\n",
    "        mp = {}\n",
    "        def bound(i,endtime):\n",
    "            if (i,endtime) in mp:\n",
    "                return mp[(i,endtime)]\n",
    "            s = 0\n",
    "            for j in range(i+1,n):\n",
    "                if events[j][0]>endtime:\n",
    "                    s += events[j][2]\n",
    "                    endtime = events[j][1]\n",
    "            # print(i,s)\n",
    "            mp[(i,endtime)]=s\n",
    "            return s\n",
    "        dp = {}\n",
    "        def dfs(i,endtime,cur_add):\n",
    "            \n",
    "            if i>=n:\n",
    "                return 0\n",
    "            elif cur_add<=0:\n",
    "                return 0\n",
    "            elif (i,endtime,cur_add) in dp:\n",
    "                return dp[(i,endtime,cur_add)]\n",
    "            b = dfs(i+1,endtime,cur_add)\n",
    "            if endtime<events[i][0]:\n",
    "                b = max(b,dfs(i+1,events[i][1],cur_add-1)+events[i][2])\n",
    "            dp[(i,endtime,cur_add)]=b\n",
    "            return b\n",
    "        \n",
    "        return dfs(0,0,k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        dp = {}\n",
    "        meetings = collections.defaultdict(list)\n",
    "        # events.append([0,0,0])\n",
    "        for start,end,value in events:\n",
    "            meetings[end].append((start,end,value))\n",
    "        events.sort(key = lambda x: x[1])\n",
    "        \n",
    "        def find(day):\n",
    "            lo,hi = 0,len(events)-1\n",
    "            \n",
    "            while lo + 1 < hi:\n",
    "                mid = (lo+hi) // 2\n",
    "                if events[mid][1] < day:\n",
    "                    lo = mid\n",
    "                else:\n",
    "                    hi = mid\n",
    "            \n",
    "            if events[hi][1] < day: return events[hi][1]\n",
    "            if events[lo][1] < day: return events[lo][1]\n",
    "            return 0\n",
    "        \n",
    "        def memo(day,k):\n",
    "            if not day or k <= 0: return 0\n",
    "            # if day == 2 and k == 1: print(2,1)\n",
    "            if (day,k) in dp: return dp[day,k]\n",
    "            # if day == 2 and k == 1: print(2,1)\n",
    "            for start,end,value in meetings[day]:\n",
    "                prev1 = find(start)\n",
    "                prev2 = find(day)\n",
    "                # print(start,prev1,end,prev2)\n",
    "                dp[day,k] = max(dp.get((day,k),0),memo(prev2,k),memo(prev1,k-1)+value)\n",
    "            return dp[day,k]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(k+1):\n",
    "            res = max(res,memo(events[-1][1],i))\n",
    "        # print(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events = [[-j,-i,k] for i,j,k in events ]\n",
    "        events.sort(key=lambda x:[x[0],x[1]])\n",
    "        ends=[b for a,b,v in events]\n",
    "        starts=[a for a,b,v in events]\n",
    "        self.record = {}\n",
    "        nn = len(events)\n",
    "\n",
    "\n",
    "        def dp(idx,k):\n",
    "            if not k or idx==nn: return 0\n",
    "            if (idx, k) in self.record:\n",
    "                return self.record[(idx, k)]\n",
    "\n",
    "            start,end,val=events[idx]\n",
    "            idx2=bisect_left(starts, end + 1, idx,-1) -idx\n",
    "            takeIdx = val if idx2+idx >= nn else dp(idx2+ idx, k-1) + val\n",
    "            notTakeIdx=dp(idx+1,k) if idx+1<nn else 0\n",
    "            self.record[(idx, k)] = max(takeIdx,notTakeIdx)\n",
    "            return self.record[(idx, k)]\n",
    "        return dp(0,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        n = len(events)\n",
    "        def compare(x1, x2):\n",
    "            return x1[1]-x2[1]\n",
    "        events.sort(key= cmp_to_key(compare))\n",
    "        # print(events)\n",
    "        @cache\n",
    "        def dfs(cn, ck):\n",
    "            if cn < 0 or ck == 0:\n",
    "                return 0\n",
    "            res = dfs(cn-1,ck)\n",
    "            [start, end, value] = events[cn]\n",
    "            l, r = 0, cn\n",
    "            def check(m):\n",
    "                return events[m][1] < start\n",
    "            # while l < r:\n",
    "            #     m = l + (r-l)//2\n",
    "            #     if check(m):\n",
    "            #         l = m+1\n",
    "            #     else:\n",
    "            #         r = m\n",
    "            # index = l-1\n",
    "\n",
    "            index = bisect_left(events, start, key = lambda x: x[1])-1\n",
    "            \n",
    "            # print(index)\n",
    "            res = max(res, (dfs(index, ck-1) if index>=0 else 0) + value)\n",
    "\n",
    "            # while n >= 0:\n",
    "            #     n -= 1\n",
    "            #     if events[n][1] < start:\n",
    "            #         res = max(res, dfs(n,ck-1)+value)\n",
    "            #         break\n",
    "            # if n < 0:\n",
    "            #     res = max(res, value)\n",
    "            return res\n",
    "        return dfs(n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        n = len(events)\n",
    "        def compare(x1, x2):\n",
    "            return x1[1]-x2[1]\n",
    "        events.sort(key= cmp_to_key(compare))\n",
    "        # print(events)\n",
    "        @cache\n",
    "        def dfs(cn, ck):\n",
    "            if cn < 0 or ck == 0:\n",
    "                return 0\n",
    "            res = dfs(cn-1,ck)\n",
    "            [start, end, value] = events[cn]\n",
    "            l, r = 0, cn\n",
    "            def check(m):\n",
    "                return events[m][1] < start\n",
    "            while l < r:\n",
    "                m = l + (r-l)//2\n",
    "                if check(m):\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m\n",
    "            # index = bisect_left(events, start, key = lambda x: x[1])\n",
    "            index = l-1\n",
    "            # print(index)\n",
    "            res = max(res, (dfs(index, ck-1) if index>=0 else 0) + value)\n",
    "\n",
    "            # while n >= 0:\n",
    "            #     n -= 1\n",
    "            #     if events[n][1] < start:\n",
    "            #         res = max(res, dfs(n,ck-1)+value)\n",
    "            #         break\n",
    "            # if n < 0:\n",
    "            #     res = max(res, value)\n",
    "            return res\n",
    "        return dfs(n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort()\n",
    "        @cache\n",
    "        def back(cur,k):\n",
    "            if k == 0 or cur == len(events):return 0\n",
    "            return max(back(cur+1,k),back(bisect_right(events,events[cur][1],key=lambda x:x[0]),k-1)+events[cur][2])\n",
    "        return back(0,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import functools\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, e: List[List[int]], k: int) -> int:\n",
    "        # 对e的第二维从小到大排序\n",
    "        e.sort(key=lambda x: x[1])\n",
    "\n",
    "        @functools.cache # python记忆化搜索的装饰器\n",
    "        def dfs(u: int, k: int, endtime: int):\n",
    "            if u == len(e) or k == 0: return 0\n",
    "            res = dfs(u + 1, k, endtime)\n",
    "            if e[u][0] > endtime:\n",
    "                res = max(res, dfs(u + 1, k - 1, e[u][1]) + e[u][2])\n",
    "            return res\n",
    "        return dfs(0, k, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        @cache\n",
    "        def f(i, cur):\n",
    "            # if cur > k: return -inf\n",
    "            if i == n or cur == k: return 0\n",
    "            not_choose = f(i+1, cur)\n",
    "            choose = events[i][2]\n",
    "            for j in range(i+1, n):\n",
    "                if events[j][0] > events[i][1]:\n",
    "                    choose += f(j, cur+1)\n",
    "                    break\n",
    "            return max(choose, not_choose)\n",
    "        n = len(events)\n",
    "        events.sort()\n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort()\n",
    "        n = len(events)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == n or j == 0:\n",
    "                return 0\n",
    "            _, e, v = events[i]\n",
    "            return max(dfs(i + 1, j), dfs(bisect_right(range(n), e, key=lambda x: events[x][0]), j - 1) + v)\n",
    "            \n",
    "        return dfs(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda x: x[0]) # 按会议开始时间排序\n",
    "        n = len(events)\n",
    "        @cache\n",
    "        def f(i: int, j: int) -> int:\n",
    "            if i >= n or j == 0:\n",
    "                return 0\n",
    "            ans = f(i + 1, j)\n",
    "            idx = bisect_right(events, [events[i][1], inf, inf])\n",
    "            return max(ans, f(idx, j - 1) + events[i][2])\n",
    "        return f(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        # 对于当前标号cur，还剩rem空间时可获得的最大val->返回\n",
    "        @cache\n",
    "        def dfs(cur, rem) -> int:\n",
    "            # 序号超限或者空间为0，无法获得val值。返回0\n",
    "            if cur == n or rem == 0:\n",
    "                return 0\n",
    "            \n",
    "            # 如果选取当前物品，利用二分找到下一个可供选择的序号nxt，序号nxt，rem-1\n",
    "            # 也可以不选当前物品，直接dfs下一层，序号+1，rem不变\n",
    "            # 返回二者中较大值\n",
    "            for nxt in range(cur,n):\n",
    "                if events[cur][1] < events[nxt][0]:\n",
    "                    break\n",
    "            else:\n",
    "                nxt += 1\n",
    "            return max(dfs(nxt, rem-1)+events[cur][2], dfs(cur+1, rem))\n",
    "        \n",
    "        n = len(events)\n",
    "        if n == 1:\n",
    "            return events[0][2]\n",
    "        events.sort(key = lambda x: x[0])\n",
    "        return dfs(0,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        n = len(events)\n",
    "        events.sort()\n",
    "        e_start = [e[0] for e in events]\n",
    "        @cache\n",
    "        def fun(now, num):\n",
    "            if now == n or num == 0:\n",
    "                return 0\n",
    "            return max(\n",
    "                fun(now+1, num), \n",
    "                events[now][-1] + fun(bisect_right(e_start, events[now][1]), num-1)\n",
    "                )\n",
    "        return fun(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "        events.sort(key=lambda e: e[1])  # 按照结束时间排序\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, k, end_time):  # 第i个会议，还剩几次会议次数，之前会议结束时间\n",
    "            if i == len(events) or k == 0:  # 会议遍历完成，or，参会次数用尽\n",
    "                return 0\n",
    "            res = dfs(i+1, k, end_time)  # 不参加当前的会议\n",
    "            if events[i][0] > end_time:  # 当前会议i的开始时间>之前参加的结束时间\n",
    "                res = max(res,events[i][2]+dfs(i+1,  k-1, events[i][1]))\n",
    "            return res \n",
    "        return dfs(0, k, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events: List[List[int]], k: int) -> int:\n",
    "       n = len(events)\n",
    "       events.sort(key=lambda o: o[0])\n",
    "\n",
    "       def binarySearch(target: int) -> int:\n",
    "          if target < events[0][0]:\n",
    "             return 0\n",
    "          if target >= events[-1][0]:\n",
    "             return n\n",
    "          left = 0\n",
    "          right = n - 1\n",
    "          res = n\n",
    "          while left <= right:\n",
    "             mid = left + ((right - left) >> 1)\n",
    "             if events[mid][0] > target:\n",
    "                res = mid\n",
    "                right = mid - 1\n",
    "             else:\n",
    "                left = mid + 1\n",
    "          return res\n",
    "\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n or j == k:\n",
    "             return 0\n",
    "          right = binarySearch(events[i][1])\n",
    "          return max(dfs(i + 1, j), dfs(right, j + 1) + events[i][2])\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, events, k):\n",
    "        events.sort()  # 按开始时间排序\n",
    "        dp = {}  # 用于记忆化的字典\n",
    "\n",
    "        def binary_search(i):\n",
    "            # 二分查找找到第一个在 events[i][1] 之后开始的会议\n",
    "            left, right = i, len(events)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if events[mid][0] > events[i][1]:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, k):\n",
    "            if k == 0 or i == len(events):\n",
    "                return 0\n",
    "            if (i, k) in dp:\n",
    "                return dp[(i, k)]\n",
    "\n",
    "            # 选择不参加这个会议\n",
    "            ans = dfs(i + 1, k)\n",
    "\n",
    "            # 选择参加这个会议\n",
    "            j = binary_search(i)  # 找到下一个可以参加的会议\n",
    "            ans = max(ans, events[i][2] + dfs(j, k - 1))\n",
    "\n",
    "            dp[(i, k)] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, k)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
